package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         208,
		Discription: "实现前缀树",
		Level:       2,
		Labels: map[string]int{
			"前缀树": 1,
		},
	})
}

// Trie 一个byte一个节点，没有压缩；假如没有对应byte的子节点，就一路创建下去
type Trie struct {
	root *TrieNode
}

type TrieNode struct {
	children map[byte]*TrieNode
	hasValue bool
}

func Constructor3() Trie {
	return Trie{
		root: &TrieNode{
			children: make(map[byte]*TrieNode, 0),
			hasValue: false,
		},
	}
}

func (trie *Trie) Insert(word string) {
	cur := trie.root
	for i := 0; i < len(word); i++ {
		ch := word[i]
		_, exist := cur.children[ch]
		if !exist {
			cur.children[ch] = &TrieNode{
				children: make(map[byte]*TrieNode),
			}
		}
		cur = cur.children[ch]
	}
	//整个word遍历完后，最后的节点要标为有值
	cur.hasValue = true
}

func (trie *Trie) Search(word string) bool {
	cur := trie.root
	for i := 0; i < len(word); i++ {
		ch := word[i]
		child, exist := cur.children[ch]
		if !exist {
			return false
		}
		cur = child
	}
	return cur.hasValue
}

func (trie *Trie) StartsWith(prefix string) bool {
	cur := trie.root
	for i := 0; i < len(prefix); i++ {
		ch := prefix[i]
		child, exist := cur.children[ch]
		if !exist {
			return false
		}
		cur = child
	}
	return true
}

/**
 * Your Trie object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Insert(word);
 * param_2 := obj.Search(word);
 * param_3 := obj.StartsWith(prefix);
 */
